package demo5;

import java.util.*;

class Node {
    public int val;
    public Node prev;
    public Node next;
    public Node child;
};

public class Solution {

//    //1.字符串的排列(字典 + 窗口)
//    public boolean checkInclusion(String s1, String s2) {
//        int len1 = s1.length();
//        int len2 = s2.length();
//        //统计s1每个字符出现的次数
//        int[] map = new int[26];
//        for(int i = 0; i < len1; i++) {
//            map[s1.charAt(i) - 'a']++;
//        }
//        for(int i = 0; i < len2; i++) {
//            if(map[s2.charAt(i) - 'a'] > 0) {
//                //遍历s2中每个字符，发现相同字符就开始使用窗口进行检验
//                int[] mapTmp = Arrays.copyOf(map, map.length);
//                for(int cur = i; cur < len2; cur++) {
//                    if(mapTmp[s2.charAt(cur) - 'a'] <= 0) {
//                        break;
//                    } else {
//                        mapTmp[s2.charAt(cur) - 'a']--;
//                    }
//                }
//                //遍历一遍mapTmp，若还出现>0的数字，就说明不是
//                int j = 0;
//                for(; j < 26; j++) {
//                    if(mapTmp[j] > 0) {
//                        break;
//                    }
//                }
//                if(j == 26) {
//                    return true;
//                }
//            }
//        }
//        return false;
//    }

    //字符串的排列(滚动字典)
//    public boolean checkInclusion(String s1, String s2) {
//        int len1 = s1.length();
//        int len2 = s2.length();
//        if(len1 > len2) {
//            return false;
//        }
//        int[] map1 = new int[26];
//        int[] map2 = new int[26];
//        //在两个窗口大小都为s1的长度
//        for(int i = 0; i < len1; i++) {
//            map1[s1.charAt(i) - 'a']++;
//            map2[s2.charAt(i) - 'a']++;
//        }
//
//        for(int i = len1; i < len2; i++) {
//            if(Arrays.equals(map1, map2)) {
//                return true;
//            }
//            //窗口右移
//            map2[s2.charAt(i) - 'a']++;//进入窗口的单词+1
//            map2[s2.charAt(i - len1) - 'a']--;//出去的-1
//        }
//        return Arrays.equals(map1, map2);//还有最后一个区间
//    }

    //2.数组的相对排序(桶排序 + 哈希)
    public int[] relativeSortArray(int[] arr1, int[] arr2) {
        int[] map = new int[1001];
        for(int i = 0; i < arr1.length; i++) {
            map[arr1[i]]++;
        }
        int[] ret = new int[arr1.length];
        int index = 0;
        for(int i = 0; i < arr2.length; i++) {
            while(map[arr2[i]] != 0) {
                ret[index++] = arr2[i];
                map[arr2[i]]--;
            }
        }
        for(int i = 0; i <= 1000; i++) {
            while(map[i] != 0) {
                ret[index++] = i;
                map[i]--;
            }
        }
        return ret;
    }

    //3.扁平化多级双向链表(递归)
//    public Node flatten(Node head) {
//        if(head == null) {
//            return head;
//        }
//        //用cur去找带有child结点的结点
//        Node cur = head;
//        while(cur.child == null) {
//            cur = cur.next;
//            if(cur == null) { //递归结束
//                return head;
//            }
//        }
//        //找到了，记录当前结点的下一个结点
//        Node curNextNext = cur.next;
//        //递归的去找当前结点的下一个结点
//        Node curNext = flatten(cur.child);
//        //找到了后,进行拼接
//        cur.next = curNext;
//        curNext.prev = cur;
//        cur.child = null;
//        //找到child的结束位置，连接curNextNext
//        while(cur.next != null) {
//            cur = cur.next;
//        }
//        cur.next = curNextNext;
//        if(curNextNext != null) {//有可能结点长度为1
//            curNextNext.prev = cur;
//        }
//        return head;
//    }

    //4.剑指 Offer II 014. 字符串中的变位词(滚动字典)
    public boolean checkInclusion(String s1, String s2) {
        int len1 = s1.length();
        int len2 = s2.length();
        if(len1 > len2) {
            return false;
        }
        int[] map1 = new int[26];
        int[] map2 = new int[26];
        for(int i = 0; i < len1; i++) {
            map1[s1.charAt(i) - 'a']++;
            map2[s2.charAt(i) - 'a']++;
        }
        for(int i = len1; i < len2; i++) {
            if(Arrays.equals(map1, map2)) {
                return true;
            }
            map2[s2.charAt(i - len1) - 'a']--;
            map2[s2.charAt(i) - 'a']++;
        }
        return Arrays.equals(map1, map2);
    }

    //5.剑指 Offer II 028. 展平多级双向链表(二叉树)
    public Node flatten(Node head) {
        if(head == null) {
            return head;
        }
        Node cur = head;
        while(cur.child == null) {
            if(cur.next == null) {
                return head;
            }
            cur = cur.next;
        }
        Node curNext = cur.next;
        Node curChild = flatten(cur.child);
        //连接
        cur.next = curChild;
        curChild.prev = cur;
        //释放
        cur.child = null;
        //寻找尾巴
        while(cur.next != null) {
            cur = cur.next;
        }
        if(curNext != null) {
            cur.next = curNext;
            curNext.prev = cur;
        }
        return head;
    }

//    //6.剑指 Offer II 075. 数组相对排序(字典排序)
//    public int[] relativeSortArray(int[] arr1, int[] arr2) {
//        int[] map = new int[1001];
//        for(int i = 0; i < arr1.length; i++) {
//            map[arr1[i]]++;
//        }
//        int[] retArr = new int[arr1.length];
//        int index = 0;
//        for(int i = 0; i < arr2.length; i++) {
//            while(map[arr2[i]] > 0) {
//                retArr[index++] = arr2[i];
//                map[arr2[i]]--;
//            }
//        }
//        for(int i = 0; i < 1001; i++) {
//            while(map[i] > 0) {
//                retArr[index++] = i;
//                map[i]--;
//            }
//        }
//        return retArr;
//    }

    //7.剑指 Offer II 038. 每日温度(单调栈)
    public int[] dailyTemperatures(int[] temperatures) {
        //创建一个单调栈，用来存放数组元素的下标
        Stack<Integer> stack = new Stack<>();
        int[] arr = new int[temperatures.length];
        for(int i = 0; i < temperatures.length; i++) {
            if(stack.isEmpty()) {
                stack.push(i);
                continue;
            }
            while(!stack.isEmpty() && temperatures[i] > temperatures[stack.peek()]) {
                int popIndex = stack.pop();
                arr[popIndex] = i - popIndex;
            }
            stack.push(i);
        }
        return arr;
    }

    //8.接雨水(单调栈)
    public int trap(int[] height) {
        Stack<Integer> stack = new Stack<>();
        int value = 0;
        for(int right = 0; right < height.length; right++) {
            while(!stack.isEmpty() && height[right] > height[stack.peek()]) {
                int low = stack.pop();
                if(stack.isEmpty()) {
                    break;
                }
                int left = stack.peek();
                int rightHigh = height[right];
                int leftHigh = height[left];
                int lowHigh = height[low];
                value += (right - left - 1) * (Math.min(rightHigh, leftHigh) - lowHigh);
            }
            stack.push(right);
        }
        return value;
    }

    //9.验证外星语词典(不讲人话)
    public boolean isAlienSorted(String[] words, String order) {
        //建立字典映射
        int[] map = new int[26];
        for(int i = 0; i < 26; i++) {
            map[order.charAt(i) - 'a'] = i;
        }
        for(int i = 0; i < words.length - 1; i++) {
            int len1 = words[i].length();
            int len2 = words[i + 1].length();
            int min = len1 > len2 ? len2 : len1;
            int j = 0;
            for(; j < min; j++) {
                if(map[words[i].charAt(j) - 'a'] < map[words[i + 1].charAt(j) - 'a']) {
                    break;
                } else if(map[words[i].charAt(j) - 'a'] > map[words[i + 1].charAt(j) - 'a']) {
                    return false;
                }
            }
            if(j == min && len1 > len2) {
                return false;
            }
        }
        return true;
    }

    //10.剑指 Offer II 076. 数组中的第 k 大的数字(top-k)
    public int findKthLargest(int[] nums, int k) {
        PriorityQueue<Integer> queue = new PriorityQueue<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o1 - o2;
            }
        });

        for(int i = 0; i < nums.length; i++) {
            if(i < k) {
                queue.offer(nums[i]);
            } else {
                if(nums[i] > queue.peek()) {
                    queue.poll();
                    queue.offer(nums[i]);
                }
            }
        }
        return queue.peek();
    }


}
class Main {
    public static void main(String[] args) {
        String s = "aaa";
        Solution solution = new Solution();
    }
}